package com.lihui.binarysearchtree;

import sun.reflect.generics.tree.Tree;

/**
 * 功能描述
 *
 * @author wileda
 * @date 2022/11/14  20:02
 */
public class BinarySearchTree {
    public static class TreeNode{
        int value;
        TreeNode left;
        TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
    public TreeNode root;

    public boolean insert(int value){
        TreeNode node = new TreeNode(value);
        if(root == null){
            root = node;
            return true;
        }
        TreeNode current = root;
        TreeNode prev = null;
        while(current != null){
            if(current.value == value){
                return false;
            }
            prev = current;
            if(node.value < current.value){
                current = current.left;
            }else{
                current = current.right;
            }
        }
        if(value < prev.value){
            prev.left = node;
        }else {
            prev.right = node;
        }
        return true;
    }


    public boolean remove(int value){
        if(root == null){
            return false;
        }
        TreeNode current = root;
        TreeNode parent  = null;
        while(current != null) {
            if (current.value == value) {
                removeNode(parent, current);
            }
            parent = current;
            if (value < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return false;
    }

    private void removeNode(TreeNode parent, TreeNode current) {
        if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (current == parent.left) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        } else if (current.right == null) {
            if (current == root) {
                root = current.left;
            } else if (current == parent.left) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        }else {
            TreeNode target = current.right;
            TreeNode parentTarget = current;
            while(target.left != null){
                parentTarget = target;
                target = target.left;
            }
            current.value = target.value;
            if(target == parentTarget.left){
                parentTarget.left = target.right;
            }else {
                parentTarget.right = target.right;
            }
        }
    }

    public boolean search(int value){
        if(root == null){
            return false;
        }
        TreeNode current = root;
        while(current != null){
            if(current.value == value){
                return true;
            }
            if(value < current.value){
                current = current.left;
            }else{
                current = current.right;
            }
        }
        return false;
    }


    public String inorder(TreeNode node){
        StringBuilder sb = new StringBuilder();
        if(node == null){
            return sb.toString();
        }
        String left = inorder(node.left);
        sb.append(left);
        sb.append(node.value + " ");
        String right = inorder(node.right);
        sb.append(right);
        return sb.toString();
    }
}
